import java.util.*;

public class Solution {
    /**
     * 最后一块石头的重量
     * @param stones
     * @return
     */
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((a, b) -> {
            return b - a;
        });
        for (int i = 0; i < stones.length; i++) {
            priorityQueue.add(stones[i]);
        }
        while (priorityQueue.size() > 1) {
            int a = priorityQueue.poll();
            int b = priorityQueue.poll();
            if (a - b > 0) {
                priorityQueue.add(a - b);
            }
        }
        return priorityQueue.size() == 1 ? priorityQueue.poll() : 0;
    }

    /**
     * 前 k 个高频单词
     * @param words
     * @param k
     * @return
     */
    public List<String> topKFrequent(String[] words, int k) {
        // 统计单词出现次数
        Map<String, Integer> hash = new HashMap<>();
        for(String word: words) {
            hash.put(word, hash.getOrDefault(word, 0) + 1);
        }
        // 使用小根堆，存放前 k个频率最高的单词
        PriorityQueue<String> privityQueue = new PriorityQueue<>((a, b) -> {
            if (hash.get(a) == hash.get(b)) {
                return b.compareTo(a);
            } else {
                return hash.get(a) - hash.get(b);
            }
        });
        // 存放
        for(String word: hash.keySet()) {
            privityQueue.offer(word);
            if (privityQueue.size() > k) {
                privityQueue.poll();
            }
        }
        // 获取前 k 个单纯
        List<String> res = new ArrayList<>();
        while(!privityQueue.isEmpty()) {
            res.add(privityQueue.poll());
        }
        // 逆序
        Collections.reverse(res);
        return res;
    }
}

/**
 * 数据流中的第 k 个大元素
 */
class KthLargest {
    PriorityQueue<Integer> priorityQueue;
    int k;
    public KthLargest(int k, int[] nums) {
        this.k = k;
        priorityQueue = new PriorityQueue<>((a, b) -> {
            return a - b;
        });
        for (int x: nums) {
            add(x);
        }

    }
    public int add(int val) {
        priorityQueue.offer(val);
        if (priorityQueue.size() > k) {
            priorityQueue.poll();
        }
        return priorityQueue.peek();
    }
}

/**
 * 数据流的中位数
 */
class MedianFinder {
    // 使用两个堆
    PriorityQueue<Integer> minHeap; // 小根堆
    PriorityQueue<Integer> maxHeap; // 大根堆
    public MedianFinder() {
        minHeap = new PriorityQueue<>((a, b) -> b - a);
        maxHeap = new PriorityQueue<>((a, b) -> a - b);
    }

    public void addNum(int num) {
        if (minHeap.size() == maxHeap.size()) {
            if (minHeap.isEmpty()) {
                minHeap.offer(num);
            } else {
                maxHeap.offer(num);
                minHeap.offer(maxHeap.poll());
            }
        } else {
            minHeap.offer(num);
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (minHeap.size() == maxHeap.size()) {
            return (minHeap.peek() + maxHeap.peek()) / 2.0;
        } else {
            return minHeap.peek();
        }
    }
}
